package everyday;

/**
 * @author zhangmin
 * @create 2022-05-02 16:23
 *
 * 实现Trie前缀树
 * 请你实现 Trie 类：
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 *
 * 思路：
 * 类似多叉树的结构,对于每个节点只需要记录他的孩子和当前节点是否可以是结束节点即可
 */
public class Trie {
    Trie[] children;
    boolean isEnd;

    public Trie() {
        children=new Trie[26];//只有小写的26个字母
        isEnd=false;
    }

    public void insert(String word) {
        //沿着树的当前节点来向下插入每个节点中word的字符
        Trie cur = this;
        for (int i = 0; i < word.length(); i++) {
            char c=word.charAt(i);
            int index=c-'a';
            if (cur.children[index]==null){
                //表示当前的字符是前缀的第一次出现
                cur.children[index]=new Trie();
            }
            cur=cur.children[index];
        }
        //遍历完了word，将word的最后一个字符的节点设置为可以结束
        cur.isEnd=true;
    }

    public boolean search(String word) {
        //和插入类似，沿着树找，当找到节点为null时
        Trie cur=this;
        for (int i = 0; i < word.length(); i++) {
            char c=word.charAt(i);
            int index=c-'a';
            if (cur.children[index]==null){
                return false;
            }
            cur=cur.children[index];
        }
        return cur!=null&&cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        //和搜索类似，沿着树找，当找到节点为null时
        Trie cur=this;
        for (int i = 0; i < prefix.length(); i++) {
            char c=prefix.charAt(i);
            int index=c-'a';
            if (cur.children[index]==null){
                return false;
            }
            cur=cur.children[index];
        }
        return cur!=null;
    }
}
